{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #采购方案"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #two-pointers #binary-search #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #双指针 #二分查找 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: purchasePlans"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #采购方案"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "小力将 N 个零件的报价存于数组 `nums`。小力预算为 `target`，假定小力仅购买两个零件，要求购买零件的花费不超过预算，请问他有多少种采购方案。\n",
    "\n",
    "注意：答案需要以 `1e9 + 7 (1000000007)` 为底取模，如：计算初始结果为：`1000000008`，请返回 `1`\n",
    "\n",
    "\n",
    "**示例 1：**\n",
    ">输入：`nums = [2,5,3,5], target = 6`\n",
    ">\n",
    ">输出：`1`\n",
    ">\n",
    ">解释：预算内仅能购买 nums[0] 与 nums[2]。\n",
    "\n",
    "**示例 2：**\n",
    ">输入：`nums = [2,2,1,9], target = 10`\n",
    ">\n",
    ">输出：`4`\n",
    ">\n",
    ">解释：符合预算的采购方案如下：\n",
    ">nums[0] + nums[1] = 4\n",
    ">nums[0] + nums[2] = 3\n",
    ">nums[1] + nums[2] = 3\n",
    ">nums[2] + nums[3] = 10\n",
    "\n",
    "**提示：**\n",
    "- `2 <= nums.length <= 10^5`\n",
    "- `1 <= nums[i], target <= 10^5`\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [4xy4Wx](https://leetcode.cn/problems/4xy4Wx/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [4xy4Wx](https://leetcode.cn/problems/4xy4Wx/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,5,3,5]\\n6', '[2,2,1,9]\\n10']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def purchasePlans(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        \n",
    "        ans = 0\n",
    "\n",
    "        i = 0\n",
    "        while i < n - 1:\n",
    "            res = target - nums[i]\n",
    "            if nums[i] > res:\n",
    "                break\n",
    "\n",
    "            while nums[-1] > res:\n",
    "                nums.pop()\n",
    "\n",
    "            n = len(nums)\n",
    "            ans += n - i - 1\n",
    "\n",
    "            i += 1\n",
    "\n",
    "        return ans % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def purchasePlans(self, nums: List[int], target: int) -> int:\n",
    "        # res = 0\n",
    "        # nums.sort()\n",
    "        # l, r = 0, len(nums) - 1\n",
    "        #\n",
    "        # while l < r:\n",
    "        #     if nums[l] + nums[r] > target:\n",
    "        #         r -= 1\n",
    "        #     else:\n",
    "        #         res += (r - l)\n",
    "        #         l += 1\n",
    "        # return res % (10 ** 9 + 7)\n",
    "\n",
    "        nums.sort()\n",
    "        cur = deque(nums)\n",
    "        res = 0\n",
    "        for i in range(len(nums)):\n",
    "            x = target - nums[i]\n",
    "            cur.popleft()\n",
    "            if x < nums[i]:\n",
    "                continue\n",
    "            b = bisect.bisect(cur, x)\n",
    "            res = (res + b) % (10 ** 9 + 7)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def purchasePlans(self, nums: List[int], target: int) -> int:\n",
    "        from bisect import bisect_right\n",
    "        from collections import deque\n",
    "        nums.sort()\n",
    "        cur=deque(nums)\n",
    "        ans=0\n",
    "        for i in range(len(nums)):\n",
    "            X=target-nums[i]\n",
    "            cur.popleft()\n",
    "            if X<nums[i]:\n",
    "                continue\n",
    "            b=bisect_right(cur,X)+i\n",
    "            ans=(ans+b-i)%(10**9+7)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def purchasePlans(self, nums: List[int], target: int) -> int:\n",
    "        # res = 0\n",
    "        # nums.sort()\n",
    "        # l, r = 0, len(nums) - 1\n",
    "        #\n",
    "        # while l < r:\n",
    "        #     if nums[l] + nums[r] > target:\n",
    "        #         r -= 1\n",
    "        #     else:\n",
    "        #         res += (r - l)\n",
    "        #         l += 1\n",
    "        # return res % (10 ** 9 + 7)\n",
    "\n",
    "        nums.sort()\n",
    "        cur = deque(nums)\n",
    "        mod = 10 ** 9 + 7\n",
    "        res = 0\n",
    "        for i in range(len(nums)):\n",
    "            x = target - nums[i]\n",
    "            cur.popleft()\n",
    "            if x < nums[i]:\n",
    "                continue\n",
    "            b = bisect.bisect(cur, x)\n",
    "            res = (res + b) % mod\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def purchasePlans(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        total = 0\n",
    "        for i, n in enumerate(nums):\n",
    "            p = bisect.bisect(nums, target - n, 0, i)\n",
    "            total += p\n",
    "        return total % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def purchasePlans(self, nums: List[int], target: int) -> int:\n",
    "        # res = 0\n",
    "        # nums.sort()\n",
    "        # l, r = 0, len(nums) - 1\n",
    "        #\n",
    "        # while l < r:\n",
    "        #     if nums[l] + nums[r] > target:\n",
    "        #         r -= 1\n",
    "        #     else:\n",
    "        #         res += (r - l)\n",
    "        #         l += 1\n",
    "        # return res % (10 ** 9 + 7)\n",
    "\n",
    "        nums.sort()\n",
    "        cur = deque(nums)\n",
    "        res = 0\n",
    "        for i in range(len(nums)):\n",
    "            x = target - nums[i]\n",
    "            cur.popleft()\n",
    "            if x < nums[i]:\n",
    "                continue\n",
    "            b = bisect.bisect(cur, x)\n",
    "            res = (res + b) % (10 ** 9 + 7)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def purchasePlans(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        i = 0\n",
    "        j = len(nums)-1\n",
    "        while i < j:\n",
    "            if nums[i] + nums[j] > target:\n",
    "                j -= 1\n",
    "            else:\n",
    "                ans += (j-i)\n",
    "                i += 1\n",
    "        # if ans<=1000000007:\n",
    "        #     return ans\n",
    "        # else:\n",
    "        return ans%1000000007\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def purchasePlans(self, nums: List[int], target: int) -> int:\n",
    "        n=len(nums)\n",
    "        nums.sort()\n",
    "        res=0\n",
    "        if nums[0]+nums[1]>target:#最小的两个和都大于target就没必要比了\n",
    "            return res\n",
    "        i,j=0,n-1\n",
    "        while i<j:\n",
    "            while nums[i]+nums[j]>target and j>0:#每次移动j直到二者和小于等于target\n",
    "                j-=1\n",
    "            res+=(j-i) if j-i>0 else 0#防止j<i的情况\n",
    "            i+=1#移动i进行下一轮比较\n",
    "        return res%1000000007\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def purchasePlans(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        res = 0\n",
    "        l, r = 0, len(nums) - 1\n",
    "        while l < r:\n",
    "            if nums[l] + nums[r] <= target:\n",
    "                res += (r - l)\n",
    "                l += 1\n",
    "            else:\n",
    "                r -= 1\n",
    "        if res <= 1000000007:\n",
    "            return res\n",
    "        else:\n",
    "            return res % 1000000007\n",
    "               \n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # sort\n",
    "    # binary search or two pointers to get range of values that work!!!\n",
    "    # [2,3,5,5], target = 6\n",
    "    # 2, search for the first value > 6-2 = 4, which is index 2. sub 1, get index 1 = j\n",
    "    # so anything from index 0...j will work, excluding the current index i\n",
    "    # can also use 2 ptrs\n",
    "    # need to divide by 2 if using binary search, since we compte both sides...\n",
    "    def purchasePlans(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        res = 0\n",
    "        MOD = 10**9+7\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            j = bisect_right(nums, target-nums[i]) - 1\n",
    "            res += j+1 - (i <= j)\n",
    "        return res // 2 % MOD\n",
    "\n",
    "    def purchasePlans(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        res = 0\n",
    "        MOD = 10**9+7\n",
    "        n = len(nums)\n",
    "        i = 0\n",
    "        j = n-1\n",
    "        while i < j:\n",
    "            while i < j and nums[i] + nums[j] > target:\n",
    "                j -= 1\n",
    "            res += j-i\n",
    "            i += 1\n",
    "        return res % MOD\n",
    "\n",
    "    def purchasePlans(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        return sum((j := bisect_right(nums, target-nums[i])) - (i < j) for i in range(len(nums))) // 2 % (10**9+7)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def purchasePlans(self, nums: List[int], target: int) -> int:\n",
    "        # res = 0\n",
    "        # nums.sort()\n",
    "        # l, r = 0, len(nums) - 1\n",
    "        #\n",
    "        # while l < r:\n",
    "        #     if nums[l] + nums[r] > target:\n",
    "        #         r -= 1\n",
    "        #     else:\n",
    "        #         res += (r - l)\n",
    "        #         l += 1\n",
    "        # return res % (10 ** 9 + 7)\n",
    "\n",
    "        nums.sort()\n",
    "        cur = deque(nums)\n",
    "        res = 0\n",
    "        for i in range(len(nums)):\n",
    "            x = target - nums[i]\n",
    "            cur.popleft()\n",
    "            if x < nums[i]:\n",
    "                continue\n",
    "            b = bisect.bisect(cur, x)\n",
    "            res = (res + b) % (10 ** 9 + 7)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def purchasePlans(self, nums: List[int], target: int) -> int:\n",
    "        res = 0\n",
    "        nums.sort()\n",
    "        l, r = 0, len(nums) - 1\n",
    "\n",
    "        while l < r:\n",
    "            if nums[l] + nums[r] > target:\n",
    "                r -= 1\n",
    "            else:\n",
    "                res += (r - l)\n",
    "                l += 1\n",
    "        return res % (10 ** 9 + 7)\n",
    "        \n",
    "        \"\"\"5.94% / 100% \"\"\" \n",
    "        # nums.sort()\n",
    "        # cur = deque(nums)\n",
    "        # mod = 10 ** 9 + 7\n",
    "        # res = 0\n",
    "        # for i in range(len(nums)):\n",
    "        #     x = target - nums[i]\n",
    "        #     cur.popleft()\n",
    "        #     if x < nums[i]:\n",
    "        #         continue\n",
    "        #     b = bisect.bisect(cur, x)\n",
    "        #     res = (res + b) % mod\n",
    "        # return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Python3 排序+ 双指针模拟\n",
    "class Solution:\n",
    "    def purchasePlans(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        nlen = len(nums)\n",
    "        l,r = 0,nlen-1\n",
    "        res = 0\n",
    "        while l < r:\n",
    "            t = nums[l] + nums[r]\n",
    "            if t > target:\n",
    "                r -= 1\n",
    "            else:\n",
    "                res += r-l\n",
    "                l += 1\n",
    "        return res % 1000000007\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def purchasePlans(self, nums: List[int], target: int) -> int:\n",
    "        #巧妙思路:排好序后，一个指针指向第一个，一个指针指向最后一个数组，如果第一个加上最后一个的和都小于目标值，那么中间的值必然都符合并且让第一个指针往后移，例如：2，3，5，5，目标值是7，如果第一个加上最后一个的值是大于目标值的，则让最后一个值的指针往前移\n",
    "        nums.sort()\n",
    "        i=0\n",
    "        j=len(nums)-1\n",
    "        count=0\n",
    "        while i<j:\n",
    "            if nums[i]+nums[j]<=target:\n",
    "                count=count+j-i\n",
    "                i=i+1\n",
    "            else:\n",
    "                j=j-1\n",
    "        return count % 1000000007\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        #这个方法会超时\n",
    "        # sum=0\n",
    "        # for i in range(len(nums)):\n",
    "            \n",
    "        #     for j in range(i+1,len(nums)):\n",
    "               \n",
    "        #         if nums[i]+nums[j]<=target:\n",
    "                    \n",
    "        #             sum=sum+1\n",
    "        #             print(j,sum)\n",
    "                    \n",
    "        # return sum\n",
    "\n",
    "\n",
    "\n",
    "    #         self.bansearch(nums,i+1,n,target-i)\n",
    "    #     return sum\n",
    "\n",
    "\n",
    "    # def bansearch(self,nums,left,right,target1):\n",
    "    #     sum=0\n",
    "    #     while left<=right:\n",
    "    #         mid=(left+right)//2\n",
    "    #         if nums[mid] <= target1:\n",
    "    #            sum=sum+1\n",
    "    #         else:\n",
    "    #             right=mid-1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def purchasePlans(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        i = 0\n",
    "        j = len(nums)-1\n",
    "        while i < j:\n",
    "            if nums[i] + nums[j] > target:\n",
    "                j -= 1\n",
    "            else:\n",
    "                ans += (j-i)\n",
    "                i += 1\n",
    "        if ans<=1000000007:\n",
    "            return ans\n",
    "        else:\n",
    "            return ans%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def purchasePlans(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        ans=0\n",
    "        i=0\n",
    "        j=len(nums)-1\n",
    "        while i<j:\n",
    "            if nums[i]+nums[j]>target:\n",
    "                j-=1\n",
    "            else:\n",
    "                ans+=(j-i)\n",
    "                i+=1\n",
    "        return int(ans%(1e9+7))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def purchasePlans(self, nums: List[int], target: int) -> int:\n",
    "        base = 10**9 + 7\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "\n",
    "        def binary_search(begin, end, t):\n",
    "            if begin == end:\n",
    "                return 1 if t >= nums[begin] else 0\n",
    "\n",
    "            left, right = begin, end\n",
    "            res = -1\n",
    "            while left <= right:\n",
    "                mid = left + (right - left) // 2\n",
    "                if nums[mid] <= t:\n",
    "                    res = mid\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid - 1\n",
    "            if res == -1:\n",
    "                return 0\n",
    "            return res - begin + 1\n",
    "\n",
    "        for i in range(len(nums) - 1):\n",
    "            s_num = nums[i]\n",
    "            t_num = target - s_num\n",
    "            # 这里进行二分查找 [i + 1, len(nums) - 1]\n",
    "            ans += binary_search(i + 1, len(nums) - 1, t_num)\n",
    "\n",
    "        return ans % base\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def purchasePlans(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        #定义双指针i，j\n",
    "        i = 0\n",
    "        j=len(nums)-1\n",
    "        ans = 0\n",
    "        while i<j:\n",
    "            if nums[i]+nums[j]<=target:\n",
    "                ans += (j-i)\n",
    "                i += 1\n",
    "            else:\n",
    "                j -= 1\n",
    "        if ans < 1000000007 :\n",
    "            return ans\n",
    "        else:\n",
    "            return ans%1000000007\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def purchasePlans(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        result=0\n",
    "        l=0\n",
    "        r=len(nums)-1\n",
    "        while(l<r):\n",
    "            if l>0 and nums[l]==nums[l-1]:\n",
    "                result+=r-l\n",
    "                l+=1\n",
    "                continue\n",
    "            while(nums[l]+nums[r]>target and r>l):\n",
    "                r-=1\n",
    "            if(l>=r):\n",
    "                break\n",
    "            result+=r-l\n",
    "            l+=1\n",
    "        return result%1000000007\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def purchasePlans(self, nums: List[int], target: int) -> int:\n",
    "        nums = sorted(nums)\n",
    "        res = 0\n",
    "        ans = 1000000007\n",
    "        p1, p2 = 0, len(nums) - 1\n",
    "        while p1 <= p2:\n",
    "            if nums[p1] + nums[p2] <= target:\n",
    "                res %=  ans\n",
    "                res += p2 - p1\n",
    "                p1 += 1\n",
    "            else:\n",
    "                p2 -= 1\n",
    "        return res % ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers.sortedlist import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def purchasePlans(self, nums: List[int], target: int) -> int:\n",
    "        nums = SortedList(nums)\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        mod = 1000000007\n",
    "        for i in range(1, n):\n",
    "            if target - nums[i] <= 0:\n",
    "                break\n",
    "            num = nums.bisect_right(target - nums[i])\n",
    "            num = min(num, i)\n",
    "            ans += num\n",
    "            ans %= mod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def purchasePlans(self, nums: List[int], target: int) -> int:\n",
    "        # res = 0\n",
    "        # nums.sort()\n",
    "        # l, r = 0, len(nums) - 1\n",
    "        #\n",
    "        # while l < r:\n",
    "        #     if nums[l] + nums[r] > target:\n",
    "        #         r -= 1\n",
    "        #     else:\n",
    "        #         res += (r - l)\n",
    "        #         l += 1\n",
    "        # return res % (10 ** 9 + 7)\n",
    "\n",
    "        nums.sort()\n",
    "        cur = deque(nums)\n",
    "        res = 0\n",
    "        for i in range(len(nums)):\n",
    "            x = target - nums[i]\n",
    "            cur.popleft()\n",
    "            if x < nums[i]:\n",
    "                break\n",
    "            b = bisect.bisect(cur, x)\n",
    "            res = (res + b) % (10 ** 9 + 7)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def purchasePlans(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        count = 0\n",
    "        MOD = 1000000007\n",
    "        \n",
    "        left, right = 0, len(nums) - 1\n",
    "        while left < right:\n",
    "            if nums[left] + nums[right] <= target:\n",
    "                count += (right - left)\n",
    "                left += 1\n",
    "            else:\n",
    "                right -= 1\n",
    "        \n",
    "        return count % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def purchasePlans(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        ans=0\n",
    "        i=0\n",
    "        j=len(nums)-1\n",
    "        while i<j:\n",
    "            if nums[i]+nums[j]>target:\n",
    "                j-=1\n",
    "            else:\n",
    "                ans+=(j-i)\n",
    "                i+=1\n",
    "        return int(ans%(1e9+7))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def purchasePlans(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        m_row = len(nums)\n",
    "        n_col = len(nums)\n",
    "        i, j = 0, n_col - 1\n",
    "        res = 0\n",
    "        while(j >= 0 and i < m_row):\n",
    "            if nums[i] + nums[j] <= target:\n",
    "                if j >= i:\n",
    "                    res = res + j\n",
    "                else:\n",
    "                    res = res + (j + 1)\n",
    "                i = i + 1\n",
    "            else:\n",
    "                j = j - 1\n",
    "        res = res // 2\n",
    "        return res % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def purchasePlans(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        result=0\n",
    "        l=0\n",
    "        r=len(nums)-1\n",
    "        while(l<r):\n",
    "            while(nums[l]+nums[r]>target and r>l):\n",
    "                r-=1\n",
    "            if(l>=r):\n",
    "                break\n",
    "            result+=r-l\n",
    "            l+=1\n",
    "        return result%1000000007\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def purchasePlans(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        i = 0\n",
    "        j = n - 1\n",
    "        while i < j:\n",
    "            while j > i and nums[i] + nums[j] > target:\n",
    "                j -= 1\n",
    "            ans += j - i\n",
    "            i += 1\n",
    "        return ans % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "### my:数组+前缀和\n",
    "class Solution:\n",
    "    def purchasePlans(self, nums: List[int], target: int) -> int:\n",
    "        arr = [0] * (target)\n",
    "        for num in nums:\n",
    "            if num >= target:\n",
    "                continue\n",
    "            arr[num] += 1\n",
    "\n",
    "        for i in range(1, target):\n",
    "            arr[i] += arr[i - 1]\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(1, target // 2 + 1):\n",
    "        # i=0\n",
    "        # while i<target//2+1:\n",
    "        #     while i<target//2+1 and arr[i]==0:\n",
    "        #         i+=1\n",
    "            left = arr[i] - arr[i - 1]\n",
    "            right = arr[target - i] - arr[i]\n",
    "            if left:\n",
    "                ### +left-1错误（是arr[i]的统计个数里面取两个相同元素的组合数计算）\n",
    "                # ans += left * right + left - 1  45/51--pass\n",
    "                ans+=left*right+(left*(left-1))//2 ###(left*(left-1))//2 相同元素的组合方案数\n",
    "            # i+=1\n",
    "        return ans%(10**9+7)\n",
    "\n",
    "# ### 网：双指针\n",
    "# class Solution:\n",
    "#     def purchasePlans(self, nums: List[int], target: int) -> int:\n",
    "#         nums=sorted(nums)\n",
    "#         n=len(nums)\n",
    "#         ans=0\n",
    "#         i,j=0,n-1\n",
    "#         while i<j:\n",
    "#             if nums[i]+nums[j]>target:\n",
    "#                 j-=1\n",
    "#             else:\n",
    "#                 ans+=(j-i)\n",
    "#                 i+=1\n",
    "#         return ans%(10**9+7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def purchasePlans(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        left = 0\n",
    "        right = len(nums) -1\n",
    "        res = 0\n",
    "        while left < right:\n",
    "            if nums[left] + nums[right] <=target:\n",
    "                res+=right -left\n",
    "                left+=1\n",
    "            else:\n",
    "                right-=1\n",
    "        return res % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# ### 45/51--pass(my)\n",
    "# class Solution:\n",
    "#     def purchasePlans(self, nums: List[int], target: int) -> int:\n",
    "#         arr = [0] * (target)\n",
    "#         for num in nums:\n",
    "#             if num >= target:\n",
    "#                 continue\n",
    "#             arr[num] += 1\n",
    "\n",
    "#         for i in range(1, target):\n",
    "#             arr[i] += arr[i - 1]\n",
    "\n",
    "#         ans = 0\n",
    "#         for i in range(1, target // 2 + 1):\n",
    "#         # i=0\n",
    "#         # while i<target//2+1:\n",
    "#         #     while i<target//2+1 and arr[i]==0:\n",
    "#         #         i+=1\n",
    "#             left = arr[i] - arr[i - 1]\n",
    "#             right = arr[target - i] - arr[i]\n",
    "#             if left:\n",
    "#                 ans += left * right + left - 1\n",
    "#             # i+=1\n",
    "#         return ans%(10**9+7)\n",
    "\n",
    "### 网：双指针\n",
    "class Solution:\n",
    "    def purchasePlans(self, nums: List[int], target: int) -> int:\n",
    "        nums=sorted(nums)\n",
    "        n=len(nums)\n",
    "        ans=0\n",
    "        i,j=0,n-1\n",
    "        while i<j:\n",
    "            if nums[i]+nums[j]>target:\n",
    "                j-=1\n",
    "            else:\n",
    "                ans+=(j-i)\n",
    "                i+=1\n",
    "        return ans%(10**9+7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def purchasePlans(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        res = 0\n",
    "        MOD_NUM = 1e9 + 7\n",
    "        low, high = 0, len(nums) - 1\n",
    "        while low < high:\n",
    "            if nums[low] + nums[high] > target:\n",
    "                high -= 1\n",
    "            else:\n",
    "                res += high - low\n",
    "                low += 1\n",
    "        return int(res % MOD_NUM)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def purchasePlans(self, nums: List[int], target: int) -> int:\n",
    "        # 先排序\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        left, right = 0, len(nums) - 1\n",
    "        while left < right:\n",
    "            tmp = nums[left] + nums[right]\n",
    "            if tmp <= target:\n",
    "                # right满足条件，left 和 right及right左边的数组合都满足条件\n",
    "                ans += right - left\n",
    "                # 下一轮，left要右移\n",
    "                left += 1\n",
    "            else:\n",
    "                # right太大了，right左移\n",
    "                right -= 1\n",
    "        return int(ans%(1e9 + 7))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def purchasePlans(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort(reverse=True)\n",
    "        c=0\n",
    "        x=0\n",
    "        y=len(nums)-1\n",
    "        while y<len(nums) and x<y:\n",
    "            if nums[x]+nums[y]>target:\n",
    "                x+=1\n",
    "            else:\n",
    "                c+=y-x\n",
    "                y-=1\n",
    "        return c % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def purchasePlans(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            x = target - nums[i]\n",
    "            if x <= 0:\n",
    "                break\n",
    "            l, r = i + 1, n - 1\n",
    "            while l <= r:\n",
    "                mid = (l + r) // 2\n",
    "                if nums[mid] <= x:\n",
    "                    l = mid + 1\n",
    "                else:\n",
    "                    r = mid - 1\n",
    "            ans += r - i\n",
    "        return ans % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def purchasePlans(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        result=0\n",
    "        l=0\n",
    "        r=len(nums)-1\n",
    "        while(l<r):\n",
    "            while(nums[l]+nums[r]>target and r>l):\n",
    "                r-=1\n",
    "            if(l>=r):\n",
    "                break\n",
    "            result+=r-l\n",
    "            l+=1\n",
    "        return result%1000000007\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def purchasePlans(self, nums: List[int], target: int) -> int:\n",
    "        res = 0\n",
    "        nums.sort()\n",
    "        l, r = 0, len(nums) - 1\n",
    "\n",
    "        while l < r:\n",
    "            if nums[l] + nums[r] > target:\n",
    "                r -= 1\n",
    "            else:\n",
    "                res += (r - l)\n",
    "                l += 1\n",
    "        return res % (10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def purchasePlans(self, nums: List[int], target: int) -> int:\n",
    "        i = 0\n",
    "        j = len(nums) - 1\n",
    "        ans = 0\n",
    "        nums.sort()\n",
    "        while i < j:\n",
    "            if nums[i] + nums[j] > target:\n",
    "                j -= 1\n",
    "            elif nums[i] + nums[j] <= target:\n",
    "                ans += j-i\n",
    "                i += 1\n",
    "        return ans % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def purchasePlans(self, nums: List[int], target: int) -> int:\n",
    "\n",
    "        # 二分\n",
    "        # nums.sort()\n",
    "        # total = 0\n",
    "        # for i, n in enumerate(nums):\n",
    "        #     p = bisect.bisect(nums, target - n, 0, i)\n",
    "        #     total += p\n",
    "        # return total % 1000000007\n",
    "\n",
    "\n",
    "        # 双指针\n",
    "        # 先排序\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        left, right = 0, len(nums) - 1\n",
    "        while left < right:\n",
    "            tmp = nums[left] + nums[right]\n",
    "            if tmp <= target:\n",
    "                # right满足条件，left 和 right及right左边的数组合都满足条件\n",
    "                ans += right - left\n",
    "                # 下一轮，left要右移\n",
    "                left += 1\n",
    "            else:\n",
    "                # right太大了，right左移\n",
    "                right -= 1\n",
    "        return int(ans%(1e9 + 7))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # sort\n",
    "    # binary search or two pointers to get range of values that work!!!\n",
    "    # [2,3,5,5], target = 6\n",
    "    # 2, search for the first value > 6-2 = 4, which is index 2. sub 1, get index 1 = j\n",
    "    # so anything from index 0...j will work, excluding the current index i\n",
    "    # can also use 2 ptrs\n",
    "    # need to divide by 2 if using binary search, since we compte both sides...\n",
    "    def purchasePlans(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        res = 0\n",
    "        MOD = 10**9+7\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            j = bisect_right(nums, target-nums[i]) - 1\n",
    "            res += j+1 - (i <= j)\n",
    "        return res // 2 % MOD\n",
    "\n",
    "    def purchasePlans(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        res = 0\n",
    "        MOD = 10**9+7\n",
    "        n = len(nums)\n",
    "        i = 0\n",
    "        j = n-1\n",
    "        while i < j:\n",
    "            while i < j and nums[i] + nums[j] > target:\n",
    "                j -= 1\n",
    "            res += j-i\n",
    "            i += 1\n",
    "        return res % MOD\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def purchasePlans(self, nums: List[int], target: int) -> int:\n",
    "        a = sorted(nums)\n",
    "        i = 0\n",
    "        j = len(a) - 1\n",
    "        r = 0\n",
    "        m = 10 ** 9 + 7\n",
    "        while j - i > 0:\n",
    "            while j - i > 0 and a[j] + a[i] > target:\n",
    "                j -= 1\n",
    "            if j - i <= 0:\n",
    "                return r \n",
    "            r += j - i\n",
    "            r %= m\n",
    "            i += 1\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def purchasePlans(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        ans=0\n",
    "        p1=0\n",
    "        p2=len(nums)-1\n",
    "        while p1<p2:\n",
    "            if (nums[p1]+nums[p2])>target:\n",
    "                p2-=1\n",
    "            else:\n",
    "                ans+=p2-p1\n",
    "                p1+=1\n",
    "        return int(ans%(1e9+7))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def purchasePlans(self, nums: List[int], target: int) -> int:\n",
    "        def binary_search(nums, target):\n",
    "            left = 0\n",
    "            right = len(nums)\n",
    "            while left < right:\n",
    "                mid = (left + right) // 2\n",
    "                if nums[mid] <= target:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid\n",
    "            return left\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            #if binary_search(nums[(i + 1):], nums[i]) - 1 >= 0:\n",
    "            k = binary_search(nums, target - nums[i])\n",
    "            if k > i:\n",
    "                ans = ans + k - 1\n",
    "            else:\n",
    "                ans = ans + k\n",
    "            #if target - nums[i] == nums[i]:\n",
    "            #    ans = ans + k - 1\n",
    "            #else:\n",
    "            #    ans = ans + k\n",
    "            #ans = ans + binary_search(nums[(i + 1):], target - nums[i])\n",
    "        return int((ans/2) % (1e9 + 7))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def purchasePlans(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        l, r = 0, len(nums) - 1\n",
    "        num_ways = 0\n",
    "        while l < r:\n",
    "            while l < r and nums[l] + nums[r] > target:\n",
    "                r -= 1\n",
    "            num_ways = (num_ways + r - l) % 1000000007\n",
    "            l += 1\n",
    "        return num_ways"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def purchasePlans(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        l, r = 0, n-1\n",
    "\n",
    "        while l < r:\n",
    "            while r >= 0 and nums[l] + nums[r] > target:\n",
    "                r -= 1\n",
    "            if r <= l:\n",
    "                break\n",
    "            ans = (ans + r - l) % (10**9+7)\n",
    "            l += 1\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def purchasePlans(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            pos = bisect.bisect_right(nums,target - nums[i])\n",
    "            ans += min(i,pos)\n",
    "            ans %= (10 ** 9 + 7)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def purchasePlans(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        i = 0\n",
    "        j = min(n - 1, bisect_left(nums, target))\n",
    "        while i < j:\n",
    "            while j > i and nums[i] + nums[j] > target:\n",
    "                j -= 1\n",
    "            ans += j - i\n",
    "            i += 1\n",
    "        return ans % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def purchasePlans(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        m_row = len(nums)\n",
    "        i, j = 0, m_row - 1\n",
    "        res = 0\n",
    "        while(j >= 0 and i < m_row and i < j):\n",
    "            if nums[i] + nums[j] <= target:\n",
    "                res = res + j - i\n",
    "                i = i + 1\n",
    "            else:\n",
    "                j = j - 1\n",
    "        return res % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def purchasePlans(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        i = 0\n",
    "        j = len(nums) -1\n",
    "        for i in range(len(nums)):\n",
    "            print(j)\n",
    "            while (j > i):\n",
    "                if nums[i] + nums[j] <= target:\n",
    "                    ans +=j -i\n",
    "                    break\n",
    "                j -=1\n",
    "        return ans%(1000000007)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def purchasePlans(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        i = 0\n",
    "        left = target - nums[i]\n",
    "        if left<nums[1]:\n",
    "            return 0\n",
    "        \n",
    "        s = 1\n",
    "        e = len(nums) - 1\n",
    "        mid = (s+e)//2\n",
    "        while s <= e:\n",
    "            if nums[mid] <= left:\n",
    "                s = mid + 1\n",
    "            else:\n",
    "                e = mid -1\n",
    "            mid = (s+e)//2\n",
    "        if nums[mid] > left:\n",
    "            mid -= 1\n",
    "        c = mid \n",
    "        i += 1\n",
    "        while i < mid:\n",
    "            left = target - nums[i]\n",
    "            while mid > i and nums[mid]>left:\n",
    "                mid -= 1\n",
    "            if mid == i:\n",
    "                break\n",
    "            c += mid - i\n",
    "            c = c%1000000007\n",
    "            i += 1\n",
    "        return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def purchasePlans(self, nums: List[int], target: int) -> int:\n",
    "        nums1 = sorted(nums)\n",
    "        left = 0\n",
    "        right = len(nums1)\n",
    "        result = []\n",
    "        while left < right - 1 :\n",
    "            if nums1[left] > target - nums1[left] :\n",
    "                break\n",
    "            j = bisect_right(nums1, target - nums1[left], left, right)\n",
    "            if j != left :\n",
    "                result.append(j - left - 1)\n",
    "            left += 1\n",
    "            right = j\n",
    "        return int(reduce(lambda x1, x2 : x1 + x2,result,0) % (1e9 + 7))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def purchasePlans(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        i = 0\n",
    "        j = len(nums)-1\n",
    "        while i < j:\n",
    "            if nums[i] + nums[j] > target:\n",
    "                j -= 1\n",
    "            else:\n",
    "                ans += (j-i)\n",
    "                i += 1\n",
    "        if ans<=1000000007:\n",
    "            return ans\n",
    "        else:\n",
    "            return ans%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def purchasePlans(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        res = 0\n",
    "        # 最小的两个数之和都大于target 就没有采购方案\n",
    "        if nums[0] + nums[1] > target:\n",
    "            return res\n",
    "        # 双指针\n",
    "        i, j = 0, n-1\n",
    "        while i < j:\n",
    "            # 每次移动右指针直到两数之和小于等于target\n",
    "            while nums[i] + nums[j] > target and j > 0:\n",
    "                j -= 1\n",
    "            res += (j-i) if j-i > 0 else 0\n",
    "            i += 1\n",
    "        return res % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def purchasePlans(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        result=0\n",
    "        l=0\n",
    "        r=len(nums)-1\n",
    "        while(l<r):\n",
    "            while(nums[l]+nums[r]>target and r>l):\n",
    "                r-=1\n",
    "            if(l>=r):\n",
    "                break\n",
    "            result+=r-l\n",
    "            l+=1\n",
    "        return result%1000000007\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def purchasePlans(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        l, r, ans = 0, len(nums) -1, 0\n",
    "        while l < r:\n",
    "            if nums[l] + nums[r] <= target:\n",
    "                ans += r - l\n",
    "                l += 1\n",
    "            else:\n",
    "                r -= 1\n",
    "        return ans % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def purchasePlans(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        res = 0\n",
    "        i = 0\n",
    "        j = len(nums) - 1\n",
    "        while i < j:\n",
    "            if nums[i] + nums[j] <= target:\n",
    "                res += j - i\n",
    "                i += 1\n",
    "            else:\n",
    "                j -= 1\n",
    "        \n",
    "        return res % 1000000007\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def purchasePlans(self, nums: List[int], target: int) -> int:\n",
    "        res = 0\n",
    "        if nums is None or len(nums) < 2:\n",
    "            return res\n",
    "        \n",
    "        nums.sort()\n",
    "        \n",
    "        i = 0\n",
    "        j = len(nums) - 1\n",
    "        while i < j:\n",
    "            while i < j and nums[i] + nums[j] > target:\n",
    "                j -= 1\n",
    "            \n",
    "            if i < j:\n",
    "                res += (j - i)\n",
    "            i += 1\n",
    "        \n",
    "        return res % 1000000007\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Python3 排序+ 双指针模拟\n",
    "class Solution:\n",
    "    def purchasePlans(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        nlen = len(nums)\n",
    "        l,r = 0,nlen-1\n",
    "        res = 0\n",
    "        while l < r:\n",
    "            t = nums[l] + nums[r]\n",
    "            if t > target:\n",
    "                r -= 1\n",
    "            else:\n",
    "                res += r-l\n",
    "                l += 1\n",
    "        return res % 1000000007\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def purchasePlans(self, nums: List[int], target: int) -> int:\n",
    "        def binarySearch(i, j, target, nums):\n",
    "            while j - i > 3:\n",
    "                mid = (i + j) >> 1\n",
    "                if nums[mid] > target: i = mid \n",
    "                else: j = mid\n",
    "            for k in range(i, j+1):\n",
    "                if nums[k] <= target:\n",
    "                    return k\n",
    "            return -1\n",
    "        nums.sort(reverse=True)\n",
    "        mod = 10 ** 9 + 7\n",
    "        n = len(nums)\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            pos = binarySearch(i+1, n-1, target-nums[i], nums)\n",
    "            if pos != -1:\n",
    "                res += n-pos\n",
    "        return res % mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def purchasePlans(self, nums: List[int], target: int) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        nums.sort()\n",
    "        res = 0\n",
    "        l, r = 0, len(nums)-1\n",
    "        while l < r:\n",
    "            while l < r and nums[l] + nums[r] > target:\n",
    "                r -= 1\n",
    "            res += r - l \n",
    "            l += 1\n",
    "        return res % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def purchasePlans(self, nums: List[int], target: int) -> int:\n",
    "\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        i = 0\n",
    "        j = len(nums)-1\n",
    "        while i < j:\n",
    "            if nums[i] + nums[j] > target:\n",
    "                j -= 1\n",
    "            else:\n",
    "                ans += (j-i)\n",
    "                i += 1\n",
    "        if ans<=1000000007:\n",
    "            return ans\n",
    "        else:\n",
    "            return ans%1000000007\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def purchasePlans(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        l = 0\n",
    "        r = n - 1\n",
    "        ans = 0\n",
    "        while l < r:\n",
    "            # 比target小\n",
    "            if nums[l] + nums[r] <= target:\n",
    "                ans += r - l\n",
    "                l += 1\n",
    "            # 比target大 右指针要往左 \n",
    "            else:\n",
    "                r -= 1\n",
    "        return ans % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def purchasePlans(self, nums: List[int], target: int) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        def getRes(mid, target, k):\n",
    "            return nums[mid] + k <= target\n",
    "        \n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        res = 0\n",
    "        for num, item in enumerate(nums):\n",
    "            left = num\n",
    "            right = n - 1\n",
    "            mid = left + (right - left)//2\n",
    "            while left <= right:\n",
    "                if getRes(mid, target, item):\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid - 1\n",
    "                mid = left + (right - left)//2\n",
    "            temp = left - num - 1\n",
    "            res = (res + (temp if temp >=0 else 0))%MOD\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def purchasePlans(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        i = 0\n",
    "        j = len(nums) -1\n",
    "        for i in range(len(nums)):\n",
    "            print(j)\n",
    "            while (j > i):\n",
    "                if nums[i] + nums[j] <= target:\n",
    "                    ans +=j -i\n",
    "                    break\n",
    "                j -=1\n",
    "        return ans%(10**9 + 7)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def purchasePlans(self, nums: List[int], target: int) -> int:\n",
    "        # MOD = 10**9 + 7\n",
    "        # nums.sort()\n",
    "        # res = 0\n",
    "        # l, r = 0, len(nums)-1\n",
    "        # while l < r:\n",
    "        #     while l < r and nums[l] + nums[r] > target:\n",
    "        #         r -= 1\n",
    "        #     res += r - l \n",
    "        #     l += 1\n",
    "        # return res % MOD\n",
    "\n",
    "        # ------------------------------------\n",
    "        MOD = 10**9 + 7\n",
    "        nums.sort()\n",
    "        res = 0\n",
    "        l, r = 0, len(nums)-1\n",
    "        while l < r:\n",
    "            if nums[l] + nums[r] > target:\n",
    "                r -= 1\n",
    "            else:\n",
    "                res += r - l \n",
    "                l += 1\n",
    "        return res % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def purchasePlans(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        left = 0\n",
    "        right = n-1\n",
    "\n",
    "        # print(nums)\n",
    "        number = 0\n",
    "        while right>left:\n",
    "\n",
    "            while (right>left) and (nums[left]+nums[right]>target):\n",
    "                # print(left, right, nums[left]+nums[right])\n",
    "                right-= 1\n",
    "\n",
    "            # print(left, right)\n",
    "            number += (right-left)\n",
    "            left += 1\n",
    "        return number%(10**9 + 7)\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def purchasePlans(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            l, r = -1, i\n",
    "            while l + 1 < r:\n",
    "                m = l + (r - l) // 2\n",
    "                if nums[i] + nums[m] <= target:\n",
    "                    l = m\n",
    "                else:\n",
    "                    r = m\n",
    "            ans += l + 1\n",
    "        return ans % 1000000007\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def purchasePlans(self, nums: List[int], target: int) -> int:\n",
    "        def binary_search(nums, target):\n",
    "            left = 0\n",
    "            right = len(nums)\n",
    "            while left < right:\n",
    "                mid = (left + right) // 2\n",
    "                if nums[mid] <= target:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid\n",
    "            return left\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            #if binary_search(nums[(i + 1):], nums[i]) - 1 >= 0:\n",
    "            k = binary_search(nums, target - nums[i])\n",
    "            if k > i:\n",
    "                ans = ans + k - 1\n",
    "            else:\n",
    "                ans = ans + k\n",
    "            #if target - nums[i] == nums[i]:\n",
    "            #    ans = ans + k - 1\n",
    "            #else:\n",
    "            #    ans = ans + k\n",
    "            #ans = ans + binary_search(nums[(i + 1):], target - nums[i])\n",
    "        return int((ans/2) % (1e9 + 7))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def purchasePlans(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        i = 0\n",
    "        j = len(nums) - 1\n",
    "        while i < j:\n",
    "            if nums[i] + nums[j] > target:\n",
    "                j -= 1\n",
    "            else:\n",
    "                ans += j - i\n",
    "                i += 1\n",
    "        return ans % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def purchasePlans(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        i = 0\n",
    "        j = len(nums)-1\n",
    "        if nums[0] + nums[1] > target:\n",
    "            return ans\n",
    "        while i <= j:\n",
    "            while nums[i] + nums[j] > target:\n",
    "                j -= 1\n",
    "            if i <= j:\n",
    "                ans += j - i  \n",
    "            else:\n",
    "                break\n",
    "            i += 1\n",
    "        return ans % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def purchasePlans(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        i = 0\n",
    "        j = len(nums)-1\n",
    "        count = 0\n",
    "        while i<j:\n",
    "            while nums[i] + nums[j] >target:\n",
    "                j-=1\n",
    "                if i>=j:\n",
    "                    break\n",
    "            count += j-i\n",
    "            count %= 1000000007\n",
    "            i+=1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def purchasePlans(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        left=0\n",
    "        right=len(nums)-1\n",
    "        ans=0\n",
    "        while left<right:\n",
    "            s=nums[left]+nums[right]\n",
    "            if s>target:\n",
    "                right-=1\n",
    "            else:\n",
    "                l=right-left\n",
    "                # 左边固定，一直到右边，这几个搭配都可以，但右边固定，左边变化，不一定可以，因为左边值是越来越大的\n",
    "                ans+=l\n",
    "                left+=1\n",
    "        return ans if ans<=1000000007 else ans%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def purchasePlans(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        i = 0\n",
    "        j = len(nums)-1\n",
    "        while i < j:\n",
    "            if nums[i] + nums[j] > target:\n",
    "                j -= 1\n",
    "            else:\n",
    "                ans += (j-i)\n",
    "                i += 1\n",
    "        if ans<=1000000007:\n",
    "            return ans\n",
    "        else:\n",
    "            return ans%1000000007\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def purchasePlans(self, nums: List[int], target: int) -> int:\n",
    "        from bisect import bisect_right\n",
    "        from collections import deque\n",
    "        nums.sort()\n",
    "        cur=deque(nums)\n",
    "        ans=0\n",
    "        for i in range(len(nums)-1):\n",
    "            X=target-nums[i]\n",
    "            cur.popleft()\n",
    "            if X<nums[i]:\n",
    "                continue\n",
    "            b=bisect_right(cur,X)+i\n",
    "            ans=(ans+b-i)%(10**9+7)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def purchasePlans(self, nums: List[int], target: int) -> int:\n",
    "        nums2 = [0]*(100001)\n",
    "        result = 0\n",
    "        del_nums = [0]*len(nums)\n",
    "        i=0\n",
    "        for num in nums:\n",
    "            nums2[num] +=1\n",
    "            del_nums[i] = target-num\n",
    "            i+=1\n",
    "        for i in range(1,len(nums2)):\n",
    "            nums2[i] +=nums2[i-1]\n",
    "        for num in del_nums:\n",
    "            if num*2>=target:\n",
    "                result +=nums2[num]-1\n",
    "            elif num>=0:\n",
    "                result +=nums2[num]\n",
    "        return int((result/2)%(1e9+7))\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def purchasePlans(self, nums: List[int], target: int) -> int:\n",
    "        nums2 = [0]*(100001)\n",
    "        result = 0\n",
    "        del_nums = [0]*len(nums)\n",
    "        i=0\n",
    "        for num in nums:\n",
    "            nums2[num] +=1\n",
    "            del_nums[i] = target-num\n",
    "            i+=1\n",
    "        for i in range(1,len(nums2)):\n",
    "            nums2[i] +=nums2[i-1]\n",
    "        for num in del_nums:\n",
    "            if num*2>=target:\n",
    "                result +=nums2[num]-1\n",
    "            elif num>=0:\n",
    "                result +=nums2[num]\n",
    "        return int((result/2)%(1e9+7))\n",
    "\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
